Khuất Xuất Luật là con trai của Taibuqa, lãnh tụ của bộ lạc Nãi Man. Năm 1204, Jamuqa (Trác Mộc Hợp), đối thủ người Mông Cổ của Thiết Mộc Chân (tức Thành Cát Tư Hãn sau này) đào thoát đến Nãi Man. Thiết Mộc Chân sau đó đã phát động một cuộc tấn công nhắm vào bộ lạc. Taibuqa lúc đầu do dự, coi tốt nhất là đi ra sau dãy núi Altai và tấn công người Mông Cổ từ đó. Tuy nhiên, Khuất Xuất Luật lại ủng hộ một cuộc giao tranh trực diện với người Mông Cổ. Ông đi xa đến mức coi kế hoạch của cha mình là hèn nhát. Taibuqa nhượng bộ và cho phép Khuất Xuất Luật thực hiện cuộc tấn công của mình.

Cuộc chiến là một thảm họa đối với Nãi Man. Jamuqa đã bỏ rơi họ và bỏ chạy. Taibuqa bị trọng thương và các chỉ huy chính của ông bị giết chết. Phần còn lại của bộ lạc đầu hàng Thiết Mộc Chân và được hợp nhất vào hàng ngũ Mông Cổ. Khuất Xuất Luật đào thoát ra và cùng với một vài binh sĩ Nãi Man đi về phía tây đến Kara Irtish.

Sau đó, Thành Cát Tư Hãn vẫn là mối đe dọa với Khuất Xuất Luật. Năm 1208, họ lại giáp mặt nhau một lần nữa trên chiến trường, và Khuất Xuất Luật bị đẩy xa hơn về phía tây đến Semirechye. Choáng váng trước thất bại lần thứ hai này, Khuất Xuất Luật đến nương nhờ Tây Liêu ở Balasaghun.